package mf.words.traversal;

import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import mf.tools.Tuple;

/**
 * Recovers the compressed text of a grammar-compressed file.
 */
public class wordTraverse {
	
	//help text displayed when you dont specify a file to rePair
	private final static String helpText = 
		"\nUsage: wordTraverse <file> [direction] [debug]\n"+
	    "\t<file>: Path to the file we want to traverse.\n" +
	    "\t[direction]: Direction of traversal. " +
	    "Possible values are 0 for left, 1 for right and 2 for both. " +
	    "Optional, if omitted left direction is assumed.\n"+
	    "\t[debug]: Show debugging informations. Optional.\n";
	
	//debug mode displays more informations
	private static boolean DEBUG_MODE = false;

	//ArrayList for the rules
	private static ArrayList<Tuple<Integer>> rules = new ArrayList<Tuple<Integer>>();

	//left derivations
	private static ArrayList<ArrayList<Integer>> L = new ArrayList<ArrayList<Integer>>();
	//right derivations
	private static ArrayList<ArrayList<Integer>> R = new ArrayList<ArrayList<Integer>>();
	
	/** Recover the rePaired file. */
	public static void main(String[] args) throws IOException {
		int direction = 0; //0 == left, 1 == right, 2 == both
		
		//parameter evaluation
		switch (args.length) {
		case 0:
			System.out.println(helpText);
			System.exit(1);
			break;
		case 1:
			break;
		case 2:
			direction = Integer.parseInt(args[1]);
			break;
		default:
			direction = Integer.parseInt(args[1]);
			
			if(args[2].equals("debug"))
				DEBUG_MODE = true;
			break;
		}
		
		System.out.println("Traverse\nLoading file "+args[0]+" ...");
		
		//create file reader object and quit if file doesnt exist
		FileReader fr = new FileReader(args[0]);
		
		//get number of rules
		int nr_rules = 0;
		for(int i=3; i>=0; i--) {
			nr_rules += fr.read()*(int)Math.pow(256, i);
		}
		
		//variables for the rules
		int var_num = 255+nr_rules;
		
		if(DEBUG_MODE)
			System.out.println("Grammar has "+ nr_rules + " rules.");
		
		//get block length from number of rules
		int blockLen = 1 + (int)(Math.log10(256+nr_rules)/Math.log10(256));
		
		//read the rules
		for(int i=0; i<nr_rules; i++) {
			char[] left = new char[blockLen], right = new char[blockLen];
			
			fr.read(left,0,blockLen);
			fr.read(right,0,blockLen);
			
			rules.add(new Tuple<Integer>(toNumber(left), toNumber(right)));
			
			if(DEBUG_MODE)
				System.out.println(
					"v_{"+(i+256)+"} -> " +
					(toNumber(left)<256 ? left[left.length-1] : "v_{"+toNumber(left)+"}")+
					(toNumber(right)<256 ? right[right.length-1] : "v_{"+toNumber(right)+"}")
				);
		}
		
		//variables for text reading
		char[] cur = new char[blockLen];
		int t_left = -1;
		
		//read first bytes
		fr.read(cur,0,blockLen);
		t_left = toNumber(cur);
		
		//read the rest of the file as remaining text and grammarify it
		while(true) {
			//read next bytes
			cur = new char[blockLen];
			fr.read(cur,0,blockLen);

			int t_right = toNumber(cur);
			
			if(t_right == 0)
				break;
			else {
				rules.add(new Tuple<Integer>(t_left, t_right));
				var_num++;
				t_left = var_num;
			}
			
		}
		
		if(DEBUG_MODE)
			System.out.println("Complete rule list is:\n" + rules.toString() + "\n\n");
		
		//preprocess mappings L, L_i and H. And R, R_i and W.
		preprocessMaps();
		
		//recover text from left to right
		if(direction != 1)
			System.out.println(traverseLeft(var_num) + "\n");
		//or from right to left
		if(direction != 0)
			System.out.println(traverseRight(var_num));
	}

	/** Traverse the tree from the beginning to the end. */
	private static String traverseLeft(int var_num) {
		String ret = "";
		Deque<Tuple<Integer>> T = new ArrayDeque<Tuple<Integer>>();
		int S = var_num;
		ArrayList<Integer> L_S = L(S);

		//get the first text symbol and initialize stack
		ret += (char)L_S.get(H(S)).intValue();
		T.push(new Tuple<Integer>(S, H(S)));
		
		//process stack
		while(true) {
			Tuple<Integer> Fi = T.pop();
			Integer P;
			
			//find the LCA
			if(Fi.right() > 0) {
				Fi.set(Fi.left(), Fi.right()-1);
				T.push(Fi);
				P = L(Fi.left()).get(Fi.right());
			} else 
				P = Fi.left();
			
			//P is the LCA
			Integer Pright = rules.get(P-256).right();
			if(Pright < 256)
				ret += (char)Pright.intValue();
			else {
				ArrayList<Integer> L_Pright = L(Pright);
				
				ret += (char)L_Pright.get(H(Pright)).intValue();
				T.push(new Tuple<Integer>(Pright, H(Pright)));
			}
			
			if(T.size() == 0)
				break;
		}
		
		return ret;
	}

	/** Traverse the tree from the end to the beginning. */
	private static String traverseRight(int var_num) {
		String ret = "";
		Deque<Tuple<Integer>> T = new ArrayDeque<Tuple<Integer>>();
		int S = var_num;
		ArrayList<Integer> R_S = R(S);
		
		//get the last text symbol and initialize stack
		ret += (char)R_S.get(W(S)).intValue();
		T.push(new Tuple<Integer>(S, W(S)));
		
		//process stack
		while(true) {
			Tuple<Integer> Fi = T.pop();
			Integer P;
			
			//find the LCA
			if(Fi.right() > 0) {
				Fi.set(Fi.left(), Fi.right()-1);
				T.push(Fi);
				P = R(Fi.left()).get(Fi.right());
			} else 
				P = Fi.left();
			
			//P is the LCA
			Integer Pleft = rules.get(P-256).left();
			if(Pleft < 256) 
				ret += (char)Pleft.intValue();
			else {
				ArrayList<Integer> R_Pleft = R(Pleft);

				ret += (char)R_Pleft.get(W(Pleft)).intValue();
				T.push(new Tuple<Integer>(Pleft, W(Pleft)));
			}
			
			if(T.size() == 0)
				break;
		}
		
		return ret;
	}
	
	/** Preprocess the mappings L, L_i and H as well as R, R_i and W. */
	private static void preprocessMaps() {
		for(int i=0; i<rules.size(); i++) {
			ArrayList<Integer> L_i = new ArrayList<Integer>();
			ArrayList<Integer> R_i = new ArrayList<Integer>();

			Integer l = rules.get(i).left();
			Integer r = rules.get(i).right();
			L_i.add(l);
			R_i.add(r);

			if(l>255)
				L_i.addAll(L(l));
			if(r>255)
				R_i.addAll(R(r));

			L.add(L_i);
			R.add(R_i);
		}
		
		if(DEBUG_MODE)
			System.out.println(
				"L="+L.toString()+"\n"+
				"R="+R.toString()
			);
	}
	
	/** Access to the left derivations for nonterminal F. */
	private static ArrayList<Integer> L(int F) {
		return L.get(F-256);
	}
	
	/** Returns the Length of the left derivations for nonterminal F. */
	private static int H(int F) {
		return L(F).size()-1;
	}

	/** Access to the right derivations for nonterminal F. */
	private static ArrayList<Integer> R(int F) {
		return R.get(F-256);
	}

	/** Returns the length of the right derivations for nonterminal F. */
	private static int W(int F) {
		return R(F).size()-1;
	}

	/** Turns an array of chars into a number assuming the array is a number to base 256. */
	private static int toNumber(char[] x) {
		int ret = 0;
		
		for(int i=0; i<x.length; i++)
			ret += (int)(x[i])*Math.pow(256, x.length-i-1);
		
		return ret;
	}
}
